Modified Interior-Point Method for Large-and-Sparse Low-Rank Semidefinite Programs

摘要

Semidefinite programs (SDPs) are powerful theoretical tools that have beenstudied for over two decades, but their practical use remains limited due tocomputational difficulties in solving large-scale, realistic-sized problems. Inthis paper, we describe a modified interior-point method for the efficientsolution of large-and-sparse low-rank SDPs, which finds applications in graphtheory, approximation theory, control theory, sum-of-squares, etc. Given thatthe problem data is large-and-sparse, conjugate gradients (CG) can be used toavoid forming, storing, and factoring the large and fully-dense interior-pointHessian matrix, but the resulting convergence rate is usually slow due toill-conditioning. Our central insight is that, for a rank-$k$, size-$n$ SDP,the Hessian matrix is ill-conditioned only due to a rank-$nk$ perturbation,which can be explicitly computed using a size-$n$ eigendecomposition. Weconstruct a preconditioner to "correct" the low-rank perturbation, therebyallowing preconditioned CG to solve the Hessian equation in a few tens ofiterations. This modification is incorporated within SeDuMi, and used to reducethe solution time and memory requirements of large-scale matrix-completionproblems by several orders of magnitude.